#include "link_node.h"
#include <iostream>
using namespace std;

template <typename T>
linkList<T>::linkList()
{
    lst=nullptr;
}
template <typename T>
linkList<T>::~linkList(){
    
}

template <typename T>
linkList<T>::linkList(T val)
{
    lst->val=val;
    lst->next=nullptr;
}

template <typename T>
linkList<T>::linkList(std::vector<T> &vec){
    lst=nullptr;
    for (int i = 0; i < vec.size(); i++)
    {
        addNode(vec[i]);
    }
       
}

template <typename T>
void linkList<T>::addNodeAtHead(T val){
    linkNode<T> *node=new linkNode<T>(val);
    if (lst==nullptr)
    {
        lst=node;
        return;
    }
    
    linkNode<T> *tmp=lst;
    lst=node;
    lst->next=tmp;  
}

/**
 * @brief 在列表中添加节点
 * 
 * @tparam T 数据类型
 * @param val 传入的节点的数据值
 */

template <typename T>
void linkList<T>::addNode(T val){
    linkNode<T> *node=new linkNode<T>(val);
    if (lst==nullptr)
    {
        // cout<< "lst is empty "<<endl;
        lst=node;
        return;
    }
/**
 * @brief 此处是定位最后一个节点的位置，while内的条件不能用tmp != nullptr;
 * 因为如果用tmp != nullptr;则当最后一个节点的时候，此时tmp指向的是最后一个节点的
 * next位置,即空指针，后面再把新建节点给空指针的位置，无法与链表关联；
 * 用tmp->next != nullptr做为判断最后一个节点的条件，当达到最后一个节点时，虽然tmp->next
 * 指向了空指针，但tmp此时指向的是最后一个节点。此时把新建节点挂在最后一个节点的next上，即与
 * 原有的链表关联起来了。 * 
 */
    linkNode<T> *tmp=lst;
    while (tmp->next != nullptr)
    {
        tmp=tmp->next;
    }
    tmp->next=node;
 
}

template <typename T>
void linkList<T>::showList(){
    linkNode<T> *tmp=lst;
    while (tmp!=nullptr)
    {
        cout << tmp->val << " -> ";
        tmp=tmp->next;
    }
    cout<<"NULL"<< endl;
    
}

/// @brief 
/// @tparam T 
/// @return 
template <typename T>
linkNode<T>* linkList<T>::localRvsList(){
    if(lst==nullptr || lst->next == nullptr)return lst;
    linkNode<T> *begin=nullptr,*end=nullptr;
    begin=lst;
    end=lst->next;
    while (end !=nullptr)
    {
        begin->next=end->next;
        end->next=lst;
        lst=end;
        end=begin->next;
    }
    return lst;
    
}

/**
 * @brief 头插法，
 * 
 * @return linkNode* 
 */
template <typename T>
linkNode<T>* linkList<T>::headRvsList(){
    if(lst==nullptr || lst->next == nullptr)return lst;
    linkNode<T> *tmp=nullptr,*newHead=nullptr;
    while (lst != nullptr)
    {
        tmp=lst;
        lst=lst->next;
        tmp->next=newHead;
        newHead=tmp;
    }
    lst=newHead;
    return lst;
}
/**
 * @brief 迭代法
 * 
 * @return linkNode* 
 */
template <typename T>
linkNode<T>* linkList<T>::iterRvsList(){
    if(lst==nullptr || lst->next == nullptr)return lst;
    linkNode<T> *p=nullptr,*c=lst,*n=lst->next;
    while (n!=nullptr)
    {
        c->next=p;
        p=c;
        c=n;
        n=n->next;
    }
    /**
     * @brief 最后一次迭代，c获取了最后一个节点，并没有与前面的节点关联起来，
     * 只有一个节点，因此在循环外还要把C与前面的节点关联起来。c->next=p;
     * 
     */
    c->next=p;
    lst=c;
    return lst;
}
